We present two graph-based algorithms for multiclass segmentation ofhigh-dimensional data. The algorithms use a diffuse interface model based onthe Ginzburg-Landau functional, related to total variation compressed sensingand image processing. A multiclass extension is introduced using the Gibbssimplex, with the functional's double-well potential modified to handle themulticlass case. The first algorithm minimizes the functional using a convexsplitting numerical scheme. The second algorithm is a uses a graph adaptationof the classical numerical Merriman-Bence-Osher (MBO) scheme, which alternatesbetween diffusion and thresholding. We demonstrate the performance of bothalgorithms experimentally on synthetic data, grayscale and color images, andseveral benchmark data sets such as MNIST, COIL and WebKB. We also make use offast numerical solvers for finding the eigenvectors and eigenvalues of thegraph Laplacian, and take advantage of the sparsity of the matrix. Experimentsindicate that the results are competitive with or better than the currentstate-of-the-art multiclass segmentation algorithms.
展开▼
